package medium公共结点;

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return null;
        }
        if (root == p || root == q)                              //如果和根节点相同直接返回
            return root;
        TreeNode a = lowestCommonAncestor(root.left, p, q);      //探究左树 查找 两个结点当中，最早出现的
        TreeNode b = lowestCommonAncestor(root.right, p, q);     //探究右树 查找 两个结点当中，最早出现的
        if (a != null && b != null){                             //如果在两侧 返回  这两个的根节点
            return root;
        }
        else if (a != null && b == null){                        //如果在左树侧 返回  这p、q其中一个
            return a;
        }
        else if (a == null && b !=null){                         //如果在右树侧 返回  这p、q其中一个
            return b;
        }
        else                                                     //如果没有返回空
            return null;
    }
}
